/******************************************************************************

    tree.c

    Version 7.51 

    This module contains the parse tree code.

    Copyright (c) 2002-2014  SLK Systems, all rights reserved.
    
******************************************************************************/

#include <stdio.h>
#include <stdlib.h> 
#include "SlkConstants.h"
#include "tree.h"
#include "SlkString.h"

#define FALSE       0 
#define TRUE        1 
// #define PRINTF      printf
#define PRINTF(a,b)
#undef push 
#undef pop

#define push(n,s) if (s.top > s.start) { *--s.top = n; }\
        else { puts ("tree: stack overflow"); exit(1); }

#define pop(s)   ( s.top < s.end ? *s.top++ : *s.top )

// -----------------------------------------------------------------------
// private usage
// -----------------------------------------------------------------------

PRIVATE 
node_t *
make_node ( slk_size_t  token,
            float       attribute )
{
    register
    node_t    *node;

    node = (node_t *)  calloc ( 1, sizeof ( node_t ) );
    if ( node == NULL ) {
        puts ( "make_node calloc failed\n" );
        exit (1);
    }
    node->token = token;
    if ( token == NUMBER_ ) {
        node->value = attribute;
    }
    return ( node );
}

// =======================================================================
// local usage only - tree recursives
// =======================================================================

PRIVATE 
void 
pre_order ( node_t   *tree )
{
    register
    node_t  *child,
            *sibling;

    if ( tree == NULL ) {
        return;
    }
    printf ( "%s\n", SlkGetSymbolName ( tree->token ) );
    child = tree->child; 
    if ( child != NULL ) {
        pre_order ( child );
        for ( sibling = child->sibling;  sibling;  sibling = sibling->sibling ) {
            pre_order ( sibling );
        }
    }
}


PRIVATE 
void 
show_parse_derivation_r ( node_t   *tree )
{
    register
    node_t  *child,
            *sibling;

    if ( tree == NULL ) {
        return;
    }
    printf ( "%s --> ", SlkGetSymbolName ( tree->token ) );
    child = tree->child; 
    if ( child != NULL ) {
        printf ( "%s ", SlkGetSymbolName ( child->token ) );
        for ( sibling = child->sibling;  sibling;  sibling = sibling->sibling ) {
            printf ( "%s ", SlkGetSymbolName ( sibling->token ) );
        }
        putchar ( '\n' );
        if ( SlkIsNonterminal ( child->token ) ) {
            show_parse_derivation_r ( child );
        } 
        for ( sibling = child->sibling;  sibling;  sibling = sibling->sibling ) {
            if ( SlkIsNonterminal ( sibling->token ) ) {
                show_parse_derivation_r ( sibling );
            }
        }
    } else { 
        putchar ( '\n' );
    }
}

PRIVATE 
node_t *
make_LL_branch ( tree_t *d,
                 slk_size_t  production_number )
{
    register
    slk_size_t   *rhs;
    register
    node_t       *prev = NULL;
    node_t       *child = NULL;
    slk_size_t   *lhs;
    int           length,
                  rhs_length;

    lhs = SlkGetProductionArray ( production_number );
    rhs_length = *lhs - 1;
    ++lhs;
    rhs = lhs + 1;
    for ( length = rhs_length;  length > 0;  --length, ++rhs ) {
        if ( SlkIsAction ( *rhs ) ) {
            continue;                               // skip actions
        }
        prev = make_node ( *rhs, get_attribute(d->peeker) );
        child = prev;
        for ( --length, ++rhs;  length > 0;  --length, ++rhs ) {
            if ( SlkIsAction ( *rhs ) ) {
                continue;                           // skip actions
            }
            prev->sibling = make_node ( *rhs, get_attribute(d->peeker) );
            prev->sibling->left_sibling = prev;
            prev = prev->sibling;
        }
    }
    for (;  prev;  prev = prev->left_sibling ) {
        if ( SlkIsNonterminal ( prev->token ) ) {
            push ( prev, d->parse_stack );                 // copy parsing pushes
        }
    }

    return  child;
}

// =======================================================================
// INSTANCE_METHOD - public usage through a struct
// =======================================================================

// ================ these are for SLK =======================

INSTANCE_METHOD
void    
(predict) ( tree_t *d,
            slk_size_t  production_number )
{
    register
    slk_size_t   *lhs;
    node_t       *parent;
    node_t       *child;

    if ( d->display ) {
        puts ( SlkGetProductionName ( production_number ) );
    }
    lhs = SlkGetProductionArray ( production_number );
    ++lhs;
    if ( ! d->root ) {                                    // first call
        d->root = make_node ( *lhs, get_attribute(d->peeker) );
        push ( d->root, d->parse_stack );
    }
    parent = pop ( d->parse_stack );
    child = make_LL_branch ( d, production_number );
    if ( child  &&  parent ) {
        parent->child = child;
        child->parent = parent;
    }
}

INSTANCE_METHOD
void    
(reduce) ( tree_t *d,
           slk_size_t production_number )
{
    register
    slk_size_t   *rhs;
    register
    node_t       *prev = NULL;
    node_t       *child = NULL;
    node_t       *this_child = NULL;
    slk_size_t   *lhs;
    int           length,
                  rhs_length;

    if ( d->display ) {
        puts ( SlkGetProductionName ( production_number ) );
    }
    lhs = SlkGetProductionArray ( production_number );
    rhs_length = *lhs - 1;
    ++lhs;
    rhs = lhs + 1;
    for ( length = rhs_length;  length > 0;  --length, ++rhs ) {
        if ( SlkIsAction ( *rhs ) ) {
            continue;                               // skip actions
        }
        prev = make_node ( *rhs, get_attribute(d->peeker) );
        this_child = prev;
        for ( --length, ++rhs;  length > 0;  --length, ++rhs ) {
            if ( SlkIsAction ( *rhs ) ) {
                continue;                               // skip actions
            }
            prev->sibling = make_node ( *rhs, get_attribute(d->peeker) );
            prev->sibling->left_sibling = prev;
            prev = prev->sibling;
        }
    }
    for (;  prev;  prev = prev->left_sibling ) {
        if ( SlkIsNonterminal ( prev->token ) ) {
            child = pop ( d->parse_stack );
            if ( child ) {
                PRINTF ( "pop :   %s\n", SlkGetSymbolName ( child->token ) );
                prev->child = child;
                child->parent = prev;
            } else {
                PRINTF ( "pop :   %s\n", "NULL" );
            }
        }
    }
    if ( this_child ) {
        PRINTF ( "push:   %s\n", SlkGetSymbolName ( this_child->token ) );
    } else {
        PRINTF ( "push:   %s\n", "NULL" );
    }
    push ( this_child, d->parse_stack );
    if ( production_number == 1 ) {
        d->root = make_node ( *lhs, get_attribute(d->peeker) );
        d->root->child = this_child;
        this_child->parent = d->root;
    }
}

// ================ user level methods =======================

INSTANCE_METHOD
void 
(show_tree) ( tree_t *d )
{
    pre_order ( d->root );
}

INSTANCE_METHOD
void 
(show_parse_derivation) ( tree_t *d )
{                                
    show_parse_derivation_r ( d->root );
}

// =======================================================================
// InitializeTree - public to set the tree values to the initial state
// =======================================================================

PUBLIC   
void
InitializeTree ( tree_t    *tree,
                 int        display,
                 peeker_t  *peeker )
{
    tree->display = display;
    tree->peeker = peeker; 
    tree->root = NULL;
    tree->parse_stack.top = tree->parse_stack.start + STACKSIZE - 1;
    tree->parse_stack.end = tree->parse_stack.start + STACKSIZE - 1;

    tree->predict = predict;
    tree->reduce = reduce;
    tree->show_tree = show_tree;
    tree->show_parse_derivation = show_parse_derivation;
}
